#include <iostream>
#include <string>
#include <vector>

using namespace std;

void getNext(vector<int> & next, string & p);
bool isInclude(string & haystack, string & needle);

class Solution 
{
public:
    bool repeatedSubstringPattern(string s) 
    {
        if(s.length() == 0)
        {
            return false;
        }
        string t = s + s;
        string t_sub = t.substr(1, t.length() - 2);
        return isInclude(t_sub, s);
    }
};

void getNext(vector<int> & next, string & p)
{
    int i = 0;
    int j = 1;
    next[i] = 0;

    for(; j < p.length(); j++)
    {
        while(i > 0 && p[i] != p[j])
        {
            i = next[i - 1];
        }
        if(p[i] == p[j])
        {
            i++;
            next[j] = i;
        }
    }
}

bool isInclude(string & haystack, string & needle)
{
    if(haystack.size() < needle.size())
    {
        return false;
    }
    if(needle.size() == 0)
    {
        return false;
    }

    vector<int> next(needle.length());
    getNext(next, needle);

    for(int i = 0, j = 0; i < haystack.length(); i++)
    {
        while (haystack[i] != needle[j] && j > 0)
        {
            j = next[j - 1];
        }
        if(haystack[i] == needle[j])
        {
            j++;
        }
        if(j == needle.length())
        {
            return true;
        }
    }
    return false;
}

int main()
{
    Solution s;
    // 测试用例1：可以由子串重复构成
    string s1 = "abab";
    cout << "测试1: " << s1 << " -> " << (s.repeatedSubstringPattern(s1) ? "true" : "false") << " (期望: true)" << endl;

    // 测试用例2：不可以由子串重复构成
    string s2 = "aba";
    cout << "测试2: " << s2 << " -> " << (s.repeatedSubstringPattern(s2) ? "true" : "false") << " (期望: false)" << endl;

    // 测试用例3：单字符重复
    string s3 = "aaaa";
    cout << "测试3: " << s3 << " -> " << (s.repeatedSubstringPattern(s3) ? "true" : "false") << " (期望: true)" << endl;

    // 测试用例4：空字符串
    string s4 = "";
    cout << "测试4: 空字符串 -> " << (s.repeatedSubstringPattern(s4) ? "true" : "false") << " (期望: false)" << endl;

    // 测试用例5：只有一个字符
    string s5 = "a";
    cout << "测试5: " << s5 << " -> " << (s.repeatedSubstringPattern(s5) ? "true" : "false") << " (期望: false)" << endl;

    // 测试用例6：较长的重复子串
    string s6 = "abaababaab";
    cout << "测试6: " << s6 << " -> " << (s.repeatedSubstringPattern(s6) ? "true" : "false") << " (期望: true)" << endl;

    return 0;
}
